package test;

/**
 * @author WYC
 * @version 1.0
 * @ClassName MinPalindrome
 * @date 2024/11/16 14:55
 * @description
 */
public class MinPalindrome {
    // 检查字符串是否为回文
    private static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 找到最小的回文字符串
    public static String makePalindrome(String s) {
        // 如果原始字符串已经是回文，直接返回
        if (isPalindrome(s)) {
            return s;
        }

        // 从尾部逐步检查最大回文前缀
        StringBuilder toAdd = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            if (isPalindrome(s.substring(0, i + 1))) {
                break;
            }
            // 记录需要添加的部分（从当前字符到尾部）
            toAdd.append(s.charAt(i));
        }

        // 将需要添加的部分加到原字符串的头部
        return toAdd + s;
    }

    public static void main(String[] args) {
        String input = "abcabc";
        System.out.println("原始字符串: " + input);
        System.out.println("最小回文字符串: " + makePalindrome(input));
    }
}
